⟸ Go Back ⟸

Exercise 8 (Homework 3).

(non regularity, union, complement, intersection, reverse, shift, Kleene star, homomorphism, inverse homomorphism)

What operations preserve non-regularity?

Let A and B be two non-regular languages and \sigma a homomorphism. Which of the following languages can we always assure is non-regular? Justify your answer (or give a counter-example if this is not true).

1. \bar{A}.
2. A\cup B.
3. A\cap B.
4. A\cdot B.
5. A^R.
6. A^*.
7. S(A) (recall that with S(A) we denote the shift of the language A, see Exercise 1.9).
8. \sigma(A).
9. \sigma^{-1}(A).